def build_next_table(pattern):
    if len(pattern) == 0:
        raise ValueError('pattern is empty')

    result = [-1]
    k = -1
    j = 0
    while j < len(pattern) - 1:
        if k == -1 or pattern[j] == pattern[k]:
            k += 1
            j += 1
            if pattern[j] == pattern[k]:
                result.append(result[k])
            else:
                result.append(k)
        else:
            k = result[k]
    return result


def kmp(pattern, string, next_table):
    i = 0
    j = 0
    while i < len(pattern) and j < len(string):
        if i == -1 or pattern[i] == string[j]:
            i += 1
            j += 1
        else:
            i = next_table[i]
    if i == len(pattern):
        return j - i
    else:
        return None
